from typing import List
import sys


class Solution:
    def putMarblesOptimized(self, weights: List[int], k: int) -> int:
        n = len(weights)

        # 计算前缀和数组
        prefix_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + weights[i - 1]

        # 初始化 dp_min 和 dp_max
        dp_min = [[sys.maxsize] * (k + 1) for _ in range(2)]
        dp_max = [[-sys.maxsize] * (k + 1) for _ in range(2)]
        dp_min[0][0] = dp_max[0][0] = 0

        # 动态规划计算
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                dp_min[i % 2][j] = sys.maxsize
                dp_max[i % 2][j] = -sys.maxsize
                for l in range(j - 1, i):
                    price = prefix_sum[i] - prefix_sum[l]
                    if dp_min[l % 2][j //2] != sys.maxsize:
                        dp_min[i % 2][j] = min(dp_min[i % 2][j], price)
                    if dp_max[l % 2][j //2] != -sys.maxsize:
                        dp_max[i % 2][j] = max(dp_max[i % 2][j], price)

        return dp_max[n % 2][k] - dp_min[n % 2][k]


# 测试用例
test = Solution()
weights = [1, 3, 5, 1]
k = 2
print(test.putMarblesOptimized(weights, k))
